package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

//给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，
// 使得 abs(nums[i] - nums[j]) <=t ，同时又满足 abs(i - j) <= k 。
// 如果存在则返回 true，不存在返回 false。
// 示例 1：
// 输入：nums = [1,2,3,1], k = 3, t = 0
// 输出：true
// 示例 2：
// 输入：nums = [1,0,1,1], k = 1, t = 2
// 输出：true
// 示例 3：
// 输入：nums = [1,5,9,1,5,9], k = 2, t = 3
// 输出：false
// 提示：
// 0 <= nums.length <= 2 * 104
// -231 <= nums[i] <= 231 - 1
// 0 <= k <= 104
// 0 <= t <= 231 - 1
// Related Topics 数组 桶排序 有序集合 排序 滑动窗口
// 👍 662 👎 0


public class Solution220 {
	// t : valueDiff
	// k : indexDiff
	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
		int n = nums.length;
		Map<Long, Long> map = new HashMap<>();
		long w = (long) t + 1;
		for (int i = 0; i < n; i++) {
			long id = getID(nums[i], w);
			if (map.containsKey(id)) {
				return true;
			}
			if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
				return true;
			}
			if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
				return true;
			}
			map.put(id, (long) nums[i]);
			if (i >= k) {
				map.remove(getID(nums[i - k], w));
			}
		}
		return false;
	}

	private long getID(long x, long w) {
		if (x >= 0) {
			return x / w;
		}
		return (x + 1) / w - 1;
	}


	public static void main(String[] args) {
		Solution220 solution = new Solution220();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
//		System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
	}

}
